import java.util.Hashtable;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Map.Entry;

import org.junit.Test;

import jdk.javadoc.internal.doclets.formats.html.resources.standard;

public class MyTest4 {
    @Test
    public void test1(){
        String formula = "(H)";
        System.out.println(countOfAtoms(formula));
    }
    public String countOfAtoms(String formula) {
        Stack<Hashtable<String,Integer>> stack=new Stack<Hashtable<String,Integer>>();
        stack.push(new Hashtable<String,Integer>());
        int i=0;
        while(i<formula.length()){
            if(formula.charAt(i)=='('){
                stack.push(new Hashtable<String,Integer>());
            }else if(formula.charAt(i)==')'){
                int n=0;
                int num=1;
                while(i+1<formula.length()&&formula.charAt(i+1)>='0'&&formula.charAt(i+1)<='9'){
                    i++;
                    n=n*10+formula.charAt(i)-'0';
                }
                if(n!=0){
                    num=n;
                }
                Hashtable<String,Integer> hashtable=stack.pop();
                for(Entry<String,Integer> entry:hashtable.entrySet()){
                    stack.peek().put(entry.getKey(), entry.getValue()*num+stack.peek().getOrDefault(entry.getKey(),0));
                }
            }else{
                int nums=1;
                StringBuilder sb=new StringBuilder(2);
                sb.append(formula.charAt(i));
                if(i+1<formula.length()&&formula.charAt(i+1)>='a'&&formula.charAt(i+1)<='z'){
                    i++;
                    sb.append(formula.charAt(i));
                } 
                /**                
                    if(i+1<formula.length()&&formula.charAt(i+1)>='0'&&formula.charAt(i+1)<='9'){
                    i++;
                    nums*=formula.charAt(i)-'0';
                    } 
                */
                int n=0;
                while(i+1<formula.length()&&formula.charAt(i+1)>='0'&&formula.charAt(i+1)<='9'){
                    i++;
                    n=n*10+formula.charAt(i)-'0';
                }
                if(n!=0){
                    nums=n*nums;
                }                
                stack.peek().put(sb.toString(), stack.peek().getOrDefault(sb.toString(), 0)+nums);              
            }
            i++;
        }
        StringBuilder ans=new StringBuilder(formula.length());
        TreeSet<Entry<String,Integer>> treeSet =new TreeSet<Entry<String,Integer>>((first,second)->(first.getKey().compareTo(second.getKey())));
        treeSet.addAll(stack.peek().entrySet());
        for(Entry<String,Integer> entry:treeSet){
            ans.append(entry.getKey());
            if(!entry.getValue().equals(1)){
                ans.append(entry.getValue()+"");
            }
        }
        return ans.toString();
    }
}
